#!/usr/bin/python
# coding:utf-8


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None

    def addnode(self, data):
        node = Node(data)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    def traverse(self):  #层次遍历
        if self.root is None:
            return None
        else:
            q = [self.root]
            res = [self.root.data]
            while q != []:
                pop_node = q.pop(0)
                if pop_node.left is not None:
                    q.append(pop_node.left)
                    res.append(pop_node.left.data)

                if pop_node.right is not None:
                    q.append(pop_node.right)
                    res.append(pop_node.right.data)
            return res

    def aftersort(self, node):   # 前序遍历
        result = []
        if node is None:
            return result
        result = [node.data]
        left = self.aftersort(node.left)
        right = self.aftersort(node.right)
        result = result + left + right
        return result

    def inorder(self, node):
        result = []
        if node is None:
            return result
        result = [node.data]
        left = self.inorder(node.left)
        right = self.inorder(node.right)
        result = left + result + right
        return result


    def reverseinorder(self, inorderlist):
        for i in inorderlist:
            if leftnode is None:
                leftnode = Node(i)
                continue
            elif middlenode is None:
                middlenode = Node(i)
                if leftnode is not None:
                    middlenode.left = leftnode
                continue
            elif rightnode is None:
                rightnode = Node(i)
                if middlenode is not None:
                    middlenode.right = rightnode
                continue
            else:
                if bigleftnode is None:
                    bigleftnode = middlenode
                    leftnode = middlenode
                    rightnode = 0
                    middlenode = None
                elif bigmiddlenode is None:
                    bigmiddlenode = middlenode
                    rightnode = None
                elif bigrightnode is None:
                    bigrightnode = middlenode

                if leftnode is None:
                    leftnode = Node(i)
                elif middlenode is None:
                    middlenode = Node(i)
                    if leftnode is not None:
                        middlenode.left = leftnode
                elif rightnode is None:
                    rightnode = Node(i)
                    if middlenode is not None:
                        middlenode.right = rightnode

t = Tree()
#for i in range(10):
#    t.addnode(i)
#print t.traverse()
#print t.aftersort(t.root)
# 中序排序后的 数组  [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
inorderlist = [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
t.reverseinorder(inorderlist)
print t.traverse()
